package com.leetcode;

import java.util.Arrays;

/**
 * 528. 按权重随机选择
 *
 * @author yml
 *
 *         给定一个正整数数组w ，其中w[i]代表下标 i的权重（下标从 0
 *         开始），请写一个函数pickIndex，它可以随机地获取下标 i，选取下标 i的概率与w[i]成正比。 例如，对于 w =
 *         [1, 3]，挑选下标 0 的概率为 1 / (1 + 3)= 0.25 （即，25%），而选取下标 1 的概率为 3 / (1 +
 *         3)= 0.75（即，75%）。 也就是说，选取下标 i 的概率为 w[i] / sum(w) 。
 */
public class LeetCode528 {

	static class Solution {

		public int sum;
		public int[] addUpArr; // 累计数组，可以构成一个单增的排序数组

		public Solution(int[] w) {
			this.addUpArr = new int[w.length];
			addUpArr[0] = w[0];
			for (int i = 1; i < w.length; i++) {
				addUpArr[i] = addUpArr[i - 1] + w[i];
			}

			// 熟记数组求和的方法
			sum = Arrays.stream(w).sum();
		}

		public int pickIndex() {
			// addUpArr所有的元素第一个最小，而第一个又一定大于等于1，所以随机数去[1, sum]
			int random = (int) (Math.random() * sum) + 1;

			// 二分查找
			int low = 0;
			int hight = addUpArr.length - 1;
			while (low < hight) {
				int mid = (low + hight) / 2;
				int midValue = addUpArr[mid];
				if (random > midValue) {
					low = mid + 1;
				} else {
					hight = mid;
				}
			}

			return low;
		}
	}

}
